home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / jpsrc2.zip / JDHUFF.C < prev    next >
C/C++ Source or Header  |  1991-12-11  |  8KB  |  332 lines
  1. /*
  2.  * jdhuff.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy decoding routines.
  9.  * These routines are invoked via the methods entropy_decode
  10.  * and entropy_decoder_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15.  
  16. /* Static variables to avoid passing 'round extra parameters */
  17.  
  18. static decompress_info_ptr dcinfo;
  19.  
  20. static INT32 get_buffer;    /* current bit-extraction buffer */
  21. static int bits_left;        /* # of unused bits in it */
  22.  
  23.  
  24. LOCAL void
  25. fix_huff_tbl (HUFF_TBL * htbl)
  26. /* Compute derived values for a Huffman table */
  27. {
  28.   int p, i, l, lastp, si;
  29.   char huffsize[257];
  30.   UINT16 huffcode[257];
  31.   UINT16 code;
  32.   
  33.   /* Figure 7.3.5.4.2.1: make table of Huffman code length for each symbol */
  34.   /* Note that this is in code-length order. */
  35.  
  36.   p = 0;
  37.   for (l = 1; l <= 16; l++) {
  38.     for (i = 1; i <= (int) htbl->bits[l]; i++)
  39.       huffsize[p++] = (char) l;
  40.   }
  41.   huffsize[p] = 0;
  42.   lastp = p;
  43.   
  44.   /* Figure 7.3.5.4.2.2: generate the codes themselves */
  45.   /* Note that this is in code-length order. */
  46.   
  47.   code = 0;
  48.   si = huffsize[0];
  49.   p = 0;
  50.   while (huffsize[p]) {
  51.     while (((int) huffsize[p]) == si) {
  52.       huffcode[p++] = code;
  53.       code++;
  54.     }
  55.     code <<= 1;
  56.     si++;
  57.   }
  58.   
  59.   /* Figure 7.3.5.4.2.3: generate encoding tables */
  60.   /* These are code and size indexed by symbol value */
  61.  
  62.   for (p = 0; p < lastp; p++) {
  63.     htbl->ehufco[htbl->huffval[p]] = huffcode[p];
  64.     htbl->ehufsi[htbl->huffval[p]] = huffsize[p];
  65.   }
  66.   
  67.   /* Figure 13.4.2.3.1: generate decoding tables */
  68.  
  69.   p = 0;
  70.   for (l = 1; l <= 16; l++) {
  71.     if (htbl->bits[l]) {
  72.       htbl->valptr[l] = p;    /* huffval[] index of 1st sym of code len l */
  73.       htbl->mincode[l] = huffcode[p]; /* minimum code of length l */
  74.       p += htbl->bits[l];
  75.       htbl->maxcode[l] = huffcode[p-1];    /* maximum code of length l */
  76.     } else {
  77.       htbl->maxcode[l] = -1;
  78.     }
  79.   }
  80.   htbl->maxcode[17] = 0xFFFFFL;    /* ensures huff_DECODE terminates */
  81. }
  82.  
  83.  
  84. /* Extract the next N bits from the input stream (N <= 15) */
  85.  
  86. LOCAL int
  87. get_bits (int nbits)
  88. {
  89.   int result;
  90.   
  91.   while (nbits > bits_left) {
  92.     int c = JGETC(dcinfo);
  93.     
  94.     get_buffer <<= 8;
  95.     get_buffer |= c;
  96.     bits_left += 8;
  97.     /* If it's 0xFF, check and discard stuffed zero byte */
  98.     if (c == 0xff) {
  99.       c = JGETC(dcinfo);  /* Byte stuffing */
  100.       if (c != 0)
  101.     ERREXIT1(dcinfo->emethods,
  102.          "Unexpected marker 0x%02x in compressed data", c);
  103.     }
  104.   }
  105.   
  106.   bits_left -= nbits;
  107.   result = ((int) (get_buffer >> bits_left)) & ((1 << nbits) - 1);
  108.   return result;
  109. }
  110.  
  111. /* Macro to make things go at some speed! */
  112.  
  113. #define get_bit()    (bits_left ? \
  114.              ((int) (get_buffer >> (--bits_left))) & 1 : \
  115.              get_bits(1))
  116.  
  117.  
  118. /* Figure 13.4.2.3.2: extract next coded symbol from input stream */
  119.   
  120. LOCAL int
  121. huff_DECODE (HUFF_TBL * htbl)
  122. {
  123.   int l, p;
  124.   INT32 code;
  125.   
  126.   code = get_bit();
  127.   l = 1;
  128.   while (code > htbl->maxcode[l]) {
  129.     code = (code << 1) + get_bit();
  130.     l++;
  131.   }
  132.  
  133.   /* With garbage input we may reach the sentinel value l = 17. */
  134.  
  135.   if (l > 16) {
  136.     ERREXIT(dcinfo->emethods, "Corrupted data in JPEG file");
  137.   }
  138.  
  139.   p = (int) (htbl->valptr[l] + (code - htbl->mincode[l]));
  140.   
  141.   return (int) htbl->huffval[p];
  142. }
  143.  
  144.  
  145. /* Figure 13.4.2.1.1: extend sign bit */
  146.  
  147. /* NB: on some compilers this will only work for s > 0 */
  148.  
  149. #define huff_EXTEND(x, s)    ((x) < (1 << ((s)-1)) ? \
  150.                  (x) + (-1 << (s)) + 1 : \
  151.                  (x))
  152.  
  153.  
  154. /* Decode a single block's worth of coefficients */
  155. /* Note that only the difference is returned for the DC coefficient */
  156.  
  157. LOCAL void
  158. decode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl)
  159. {
  160.   int s, k, r, n;
  161.  
  162.   /* zero out the coefficient block */
  163.  
  164.   MEMZERO((void *) block, SIZEOF(JBLOCK));
  165.   
  166.   /* Section 13.4.2.1: decode the DC coefficient difference */
  167.  
  168.   s = huff_DECODE(dctbl);
  169.   if (s) {
  170.     r = get_bits(s);
  171.     s = huff_EXTEND(r, s);
  172.   }
  173.   block[0] = s;
  174.  
  175.   /* Section 13.4.2.2: decode the AC coefficients */
  176.   
  177.   for (k = 1; k < DCTSIZE2; k++) {
  178.     r = huff_DECODE(actbl);
  179.     
  180.     s = r & 15;
  181.     n = r >> 4;
  182.     
  183.     if (s) {
  184.       k += n;
  185.       r = get_bits(s);
  186.       block[k] = huff_EXTEND(r, s);
  187.     } else {
  188.       if (n != 15)
  189.     break;
  190.       k += 15;
  191.     }
  192.   }
  193. }
  194.  
  195.  
  196. /*
  197.  * Initialize for a Huffman-compressed scan.
  198.  * This is invoked after reading the SOS marker.
  199.  */
  200.  
  201. METHODDEF void
  202. huff_decoder_init (decompress_info_ptr cinfo)
  203. {
  204.   short ci;
  205.   jpeg_component_info * compptr;
  206.  
  207.   /* Initialize static variables */
  208.   dcinfo = cinfo;
  209.   bits_left = 0;
  210.  
  211.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  212.     compptr = cinfo->cur_comp_info[ci];
  213.     /* Make sure requested tables are present */
  214.     if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
  215.     cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
  216.       ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
  217.     /* Compute derived values for Huffman tables */
  218.     /* We may do this more than once for same table, but it's not a big deal */
  219.     fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
  220.     fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  221.     /* Initialize DC predictions to 0 */
  222.     cinfo->last_dc_val[ci] = 0;
  223.   }
  224.  
  225.   /* Initialize restart stuff */
  226.   cinfo->restarts_to_go = cinfo->restart_interval;
  227.   cinfo->next_restart_num = 0;
  228. }
  229.  
  230.  
  231. /*
  232.  * Check for a restart marker & resynchronize decoder.
  233.  */
  234.  
  235. LOCAL void
  236. process_restart (decompress_info_ptr cinfo)
  237. {
  238.   int c, nbytes;
  239.   short ci;
  240.  
  241.   /* Throw away any partial unread byte */
  242.   bits_left = 0;
  243.  
  244.   /* Scan for next JPEG marker */
  245.   nbytes = 0;
  246.   do {
  247.     do {            /* skip any non-FF bytes */
  248.       nbytes++;
  249.       c = JGETC(cinfo);
  250.     } while (c != 0xFF);
  251.     do {            /* skip any duplicate FFs */
  252.       nbytes++;
  253.       c = JGETC(cinfo);
  254.     } while (c == 0xFF);
  255.   } while (c == 0);        /* repeat if it was a stuffed FF/00 */
  256.  
  257.   if (c != (RST0 + cinfo->next_restart_num))
  258.     ERREXIT2(cinfo->emethods, "Found 0x%02x marker instead of RST%d",
  259.          c, cinfo->next_restart_num);
  260.  
  261.   if (nbytes != 2)
  262.     TRACEMS2(cinfo->emethods, 1, "Skipped %d bytes before RST%d",
  263.          nbytes-2, cinfo->next_restart_num);
  264.   else
  265.     TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num);
  266.  
  267.   /* Re-initialize DC predictions to 0 */
  268.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  269.     cinfo->last_dc_val[ci] = 0;
  270.  
  271.   /* Update restart state */
  272.   cinfo->restarts_to_go = cinfo->restart_interval;
  273.   cinfo->next_restart_num++;
  274.   cinfo->next_restart_num &= 7;
  275. }
  276.  
  277.  
  278. /*
  279.  * Decode and return one MCU's worth of Huffman-compressed coefficients.
  280.  */
  281.  
  282. METHODDEF void
  283. huff_decode (decompress_info_ptr cinfo, JBLOCK *MCU_data)
  284. {
  285.   short blkn, ci;
  286.   jpeg_component_info * compptr;
  287.  
  288.   /* Account for restart interval, process restart marker if needed */
  289.   if (cinfo->restart_interval) {
  290.     if (cinfo->restarts_to_go == 0)
  291.       process_restart(cinfo);
  292.     cinfo->restarts_to_go--;
  293.   }
  294.  
  295.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  296.     ci = cinfo->MCU_membership[blkn];
  297.     compptr = cinfo->cur_comp_info[ci];
  298.     decode_one_block(MCU_data[blkn],
  299.              cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no],
  300.              cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  301.     /* Convert DC difference to actual value, update last_dc_val */
  302.     MCU_data[blkn][0] += cinfo->last_dc_val[ci];
  303.     cinfo->last_dc_val[ci] = MCU_data[blkn][0];
  304.   }
  305. }
  306.  
  307.  
  308. /*
  309.  * Finish up at the end of a Huffman-compressed scan.
  310.  */
  311.  
  312. METHODDEF void
  313. huff_decoder_term (decompress_info_ptr cinfo)
  314. {
  315.   /* No work needed */
  316. }
  317.  
  318.  
  319. /*
  320.  * The method selection routine for Huffman entropy decoding.
  321.  */
  322.  
  323. GLOBAL void
  324. jseldhuffman (decompress_info_ptr cinfo)
  325. {
  326.   if (! cinfo->arith_code) {
  327.     cinfo->methods->entropy_decoder_init = huff_decoder_init;
  328.     cinfo->methods->entropy_decode = huff_decode;
  329.     cinfo->methods->entropy_decoder_term = huff_decoder_term;
  330.   }
  331. }
  332.